package algotithm.leetcode.twopoint.interview1721;

/**
 * @author zhouyanxiang
 * @Date 2021-04-2021/4/2-22:57
 * @Title 面试题 17.21. 直方图的水量
 */
public class Solution {

    public static void main(String[] args) {
        int[] height = {0,1,0,2,1,0,1,3,2,1,2,1};
        Solution solution = new Solution();
        int trap = solution.trap(height);
        System.out.println(trap);
    }

    public int trap(int[] height) {
        if(height.length < 3) {
            return 0;
        }

        int left = 0, right = height.length - 1;
        int leftmax = height[left], rightmax = height[right];
        int res = 0;

        while(left < right){
            if(leftmax < rightmax){
                res += leftmax - height[left++];
                leftmax = Math.max(height[left], leftmax);
            }else{
                res += rightmax - height[right--];
                rightmax = Math.max(height[right], rightmax);
            }
        }

        return res;
    }
}